package com.zzz.offer.bfstree;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x, TreeNode left, TreeNode right) {
        val = x;
        this.left = left;
        this.right = right;
    }
}

public class BFSTreeNode {
    public static void main(String[] args) {

        TreeNode x = new TreeNode(1,
                new TreeNode(2, new TreeNode(3, null, null), new TreeNode(4, null, null)),
                new TreeNode(5, null, null));

        System.out.println(new BFSTreeNode().PrintFromTopToBottom(x));


    }

    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        // 存放TreeNode
        Queue<TreeNode> treeQueue = new LinkedList<>();
        treeQueue.add(root);
        // BFS
        // 整个流程是：
        // 创建队列    |  |
        // 先放入root      | 1 |
        // 从队列中 取出 1  拿到 1.left = 2   2.right = 5   放入队列    队列     | 2   5 |
        // 从队列中 取出 2  拿到 2.left = 3   2.right = 4   放入队列    队列     | 4   3   5 |
        // 从队列中 取出 5  拿到 5.left = ''  5.right = ''             队列     | 4   3 |
        // 从队列中 取出 3  拿到 3.left = ''  3.right = ''             队列     | 4 |
        // 从队列中 取出 4  拿到 4.left = ''  4.right = ''             队列     | |
        while (treeQueue.size() != 0) {
            // 取出队头元素
            TreeNode node = treeQueue.poll();  // 去除 队列 头结点，
            if (node.left != null) {
                treeQueue.add(node.left);   // 这里并没有递归，而是 直接放入 队列中
            }
            if (node.right != null) {
                treeQueue.add(node.right);
            }
            res.add(node.val);
        }
        return res;
    }
}
